In recent years, as computers and networks have advanced and prevailed rapidly, many kinds of information such as text data, image data, audio data, and the like have been digitized. Upon digitizing such information, various documents that conventionally used paper and the like are handled as digital data. However, digital data can be readily tampered with, and tampering prevention of digital data has become major concerns. For this reason, a security technique for tampering prevention has increasingly gained its importance. Hence, a method and system for detecting whether or not digital data has been tampered with or forged have been proposed.
For example, a system that exploits a digital signature is well known as a system for detecting any tampering and forgery.
Upon using a digital signature, a sender sends signature data corresponding to data together with the data, and a receiver checks the authenticity of the data by verifying the signature data. The authenticity of data is checked as follows using a Hash function and public key cryptography upon generating digital signature data.
Let Ks be a secret key, and Kp be a public key. Then, a sender makes an arithmetic operation for calculating output h with a given length (e.g., 128 bits) by compressing plaintext data M by a Hash function. The sender then makes an arithmetic operation for generating digital signature data s by converting h using secret key Ks, i.e., D(Ks, h)=s. After that, the sender sends digital signature data s and plaintext data M.
On the other hand, a receiver makes an arithmetic operation for converting received digital signature data s using public key Kp, i.e., E(Kp, s)=E(Kp, D(Ks, h″))=h″, and an arithmetic operation for calculating h′ by compressing received plaintext data M′ by the same Hash function as the sender. If h′ and h″ match, the receiver determines that received data M′ is authentic.
If plaintext data M has been tampered with between the sender and receiver, E(Kp, s)=E(Kp, D(Ks, h″))=hh″ does not match h′ obtained by compressing received plaintext data M′ using the same Hash function as the sender, thus detecting tampering.
If digital signature data s is tampered with in correspondence with tampering of plaintext data M, tampering can no longer be detected. However, in this case, plaintext data M must be calculated from h, and it is impossible to make such calculation due to unidirectionality of the Hash function. As described above, data can be correctly authenticated by the digital signature using public key cryptography and Hash function.
The Hash function will be explained below. The Hash function is used to generate a digital signature and the like at high speed. The Hash function has a function of processing plaintext data M with an arbitrary length to generate output h with a given length. Note that output h is called a Hash value (or message digest, digital fingerprint) of plaintext data M. The Hash function is required to have unidirectionality and collision resistance. The unidirectionality means that if h is given, it is computationally infeasible to calculate plaintext data M that satisfies h=H(M). The collision resistance means that if plaintext data M is given, it is computationally infeasible to calculate plaintext data M′ (M≠M′) that satisfies H(M)=H(M′), and it is computationally infeasible to calculate plaintext data M and M′ that satisfy H(M)=H(M′) and M≠M′.
As the Hash function, MD-2, MD-4, MD-5, SHA-1, RIPEMD-128, RIPEMD-160, and the like are known, and these algorithms are open to the public.
Public key cryptography will be explained below. In public key cryptography, encrypt and decrypt keys are different, the encrypt key is open to the public, and the decrypt key is held in secrecy. As features of public key cryptography,
(a) since the encrypt and decrypt keys are different and the encrypt key can be open to the public, the encrypt key need not be delivered in secrecy, and key delivery is easy;
(b) since the encrypt key of each user is open to the public, the user need only store his or her decrypt key in secrecy; and
(c) an authentication function used by the receiver to authenticate if the sender of a message is a disguised person and that message is not tampered with can be implemented.
For example, if encryption of plaintext data M using public encrypt key Kp is given by E(Kp, M) and decryption using secret decrypt key Ks is given by D(Ks, M), the public key cryptography algorithm satisfies the following two conditions. (1) If Kp is given, it is easy to calculate E(Kp, M). If Ks is given, it is easy to calculate D(Ks, M). (2) If Ks is unknown, it is computationally infeasible to determine M even if the calculation procedures of Kp and E and C=E(Kp, M) are known.
If the following condition (3) is met in addition to the above conditions (1) and (2), a secret communication can be implemented. (3) For all plaintext data M, E(Kp, M) can be defined and D(Ks, E(Kp, M))=M. That is, since Kp is open to the public, everyone can calculate E(Kp, M), but only a person who has secret key Ks can obtain M by calculating D(Ks, E(Kp, M)).
On the other hand, if the following condition (4) is met in addition to the conditions (1) and (2), an authentication communication can be implemented. (4) For all plaintext data M, D(Ks, M) can be defined and E(Kp, D(Ks, M))=M. That is, only a person who has secret key Ks can calculate D(Ks, M), and if a third party disguises himself or herself as that person who has secret key Ks by calculating D(Ks′, M) using false secret key Ks′, since E(Kp, D(Ks′, M))≠M, the receiver can confirm that the received information is an illicit one. Also, even when D(Ks, M) has been tampered with, since E(Kp, D(Ks, M)′)≠M, the receiver can confirm that the received information is an illicit one.
As typical examples that can make the secret and authentication communications, RSA cryptography, R cryptography, W cryptography, and the like are known.
Encryption and decryption of RSA cryptography which is most prevalently used today are given by:
Encryption: encrypt key (e, n) Encrypt conversion C=Me(mod n)
Decryption: decrypt key (d, n) Decrypt conversion M=Cd(mod n)
n=p·q (where p and q are large different prime numbers)
As described above, since the RSA cryptography requires power and remainder arithmetic operations in both encryption and decryption, a huge arithmetic operation volume is required compared to common key cryptography such as DES or the like, and it is difficult to attain high-speed processing.
As described above, detection of tampering and forgery in the prior art requires a digital signature in addition to digital data. Normally, a digital signature is sent while being appended to the header of digital data. However, the appended digital signature may be easily removed by format conversion of digital data. If the digital signature is removed, digital data cannot be authenticated.
A method which can solve the above problem is disclosed in Japanese Patent Laid-Open No. 10-164549 (to be referred to as patent reference 1). In patent reference 1, a signature apparatus breaks up digital information into two fields, generates a digital signature from the segmented first field, and generates signed digital information by embedding the generated digital signature in the segmented second field as a digital watermark. On the other hand, an authentication apparatus breaks up the signed digital information into the first and second fields, generates a first digital signature from the first field, and extracts a second digital signature embedded as the digital signature from the second field. If the first and second digital signatures match, it is authenticated that the digital information is free from tampering and forgery.
As described above, in order to authenticate digital data, it is important to set authentication information such as a digital signature to be inseparable from digital information. If data to be signed is image data, the method of patent reference 1 can be applied. However, if data to be signed is a document or the like, it is difficult to apply that method.